/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

function Node(val, next, random) {
  this.val = val
  this.next = next
  this.random = random
}

/**
 * @param {Node} head
 * @return {Node}
 */
export var copyRandomList = function (head) {
  if (!head) return null
  const nodeMap = new WeakMap()
  let newHead = new Node(head.val, null, head.random)
  nodeMap.set(head, newHead)

  // 拷贝链表，但random还是指向原random
  let newCur = newHead
  let cur = head.next
  while (cur) {
    const newNode = new Node(cur.val, null, cur.random)
    nodeMap.set(cur, newNode)
    newCur.next = newNode

    newCur = newCur.next
    cur = cur.next
  }
  // 拷贝random
  newCur = newHead
  while (newCur) {
    if (newCur.random) {
      newCur.random = nodeMap.get(newCur.random)
    }
    newCur = newCur.next
  }
  return newHead
}

export const copyRandomList2 = (head, cache = new WeakMap()) => {
  if (!head) return head
  if (!cache.has(head)) {
    const node = new Node(head.val)
    cache.set(head, node)

    node.random = copyRandomList(head.random, cache)
    node.next = copyRandomList(head.next, cache)
  }
  return cache.get(head)
}
